Skip to main content

Fast Fourier Transform

  • Metadata:
    • #data-science
  • #til2022 Baruch Plan
    • An international organization would be in control of all nuclear products
    • Russia rejected this plan and triggered the nuclear arms race
  • #til2022 Peace Symbol
    • Created with the combination of the semaphore letters of N and D, which stands for "nuclear disarmament"
  • First developed to detect underground nuclear tests with seismometers
    • Now it is used in most compression algorithms and signal processing
  • Fourier Transform decomposes any signal into the sum product of sine waves
    • This is done by taking a sine (and cosine) wave and multiplying it into the signal and if the area under the product is non-zero then the sine wave is correlated with the signal and a component
    • The size of the area is the relative amplitude of that sine wive
    • Sweep across all frequencies of the sine (and cosine) wave
  • Discrete Fourier Transform is used for discrete finite data which is what the seismometers record
    • Requires a high number of calculations that scales with the number of samples N2N^2
  • Fast Fourier Transform
    • Discovered by Tukey and implemented by Cooley
    • Scales with the number of samples Nlog2NNlog_2N
  • However, this wasn't discovered in time so lots of underground testing were done during the arms race because the comprehensive test ban could not be established
    • But it was, Gauss figured out Fourier Transform and FFT before Fourier and Tukey but it wasn't published nor it was written in an easily accessible writing